// TreeAndGraphs.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "..\Common\TreeHelper.h"
#include "..\Common\LinkedListNode.h"

#include <iostream>
#include <memory>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

void testIsBalancedBTree() //4.1
{
	auto root = make_shared<BinaryTreeNode<int>>(0);
	for (int i = 1; i < 15; i++)
	{
		TreeHelper::add<int>(root, i);
	}

	if (TreeHelper::isBalanced(root))
	{
		cout << "The given tree is balanced." << endl;
	}
}

shared_ptr<BinaryTreeNode<int>> sortedUniqueArrayToBalancedBinarySearchTree(vector<int>::const_iterator first,
	vector<int>::const_iterator last)
{
	auto d = distance(first, last);
	if (d == 1)
	{
		return make_shared<BinaryTreeNode<int>>(*first);
	}

	auto middle = first + (d / 2);
	auto node = make_shared<BinaryTreeNode<int>>(*middle);
	node->setLeft(sortedUniqueArrayToBalancedBinarySearchTree(first, middle));

	if (middle + 1 != last)
	{
		node->setRight(sortedUniqueArrayToBalancedBinarySearchTree(middle + 1, last));
	}
	return node;
}

void testSortedUniqueArrayToBalancedBinarySearchTree()
{
	//4.3 Given a sorted (increasing order) array with unique integer elements, write an algorithm to create
	//a binary search tree with minimal height.
	int array[] = {0, 1, 2, 3 ,4 ,5 ,6 ,7 ,8};
	vector<int> data(&array[0], &array[sizeof(array) / sizeof(int)]);

	auto ret = sortedUniqueArrayToBalancedBinarySearchTree(data.begin(), data.end());
}

shared_ptr<LinkedListNode<shared_ptr<BinaryTreeNode<int>>>> duplicate(shared_ptr<LinkedListNode<shared_ptr<BinaryTreeNode<int>>>> original)
{
	return original;
}

vector<shared_ptr<LinkedListNode<shared_ptr<BinaryTreeNode<int>>>>> binaryTreeToLinkedList(shared_ptr<BinaryTreeNode<int>> root)
{
	vector<shared_ptr<LinkedListNode<shared_ptr<BinaryTreeNode<int>>>>> ret;
	if (root->left())
	{
		auto top = ret.back();

		if (root->right())
		{
			auto branch = duplicate(ret.back());
			ret.push_back(branch);
			ret.back()->setNext(make_shared<LinkedListNode<shared_ptr<BinaryTreeNode<int>>>>(root->right()));
		}
		ret.back()->setNext(make_shared<LinkedListNode<shared_ptr<BinaryTreeNode<int>>>>(root->left()));
	}
	else if (root->right())
	{
		ret.back()->setNext(make_shared<LinkedListNode<shared_ptr<BinaryTreeNode<int>>>>(root->right()));
	}


	return ret;
}

void testBinaryTreeToLinkedList()
{
	//Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g.,
	//if you have a tree with Depth D, you'll have D linked lists).
	auto root = make_shared<BinaryTreeNode<int>>(0);
	for (int i = 1; i < 15; i++)
	{
		TreeHelper::add<int>(root, i);
	}

	binaryTreeToLinkedList(root);
}

#if 0
bool isBinarySearchTree(shared_ptr<BinaryTreeNode<int>> root, 
	shared_ptr<int> minValue = make_shared<int>(), 
	shared_ptr<int> maxValue = make_shared<int>())
{
	bool ret = true;

	if (root)
	{
		auto leftMin = make_shared<int>(numeric_limits<int>::max());
		auto leftMax = make_shared<int>(numeric_limits<int>::min());

		if (root->left())
		{
			ret = ret && 
				isBinarySearchTree(root->left(), leftMin, leftMax) && 
				*leftMax <= root->value();
		}

		auto rightMin = make_shared<int>(numeric_limits<int>::max());
		auto rightMax = make_shared<int>(numeric_limits<int>::min());

		if (root->right())
		{
			ret = ret && 
				isBinarySearchTree(root->right(), rightMin, rightMax) && 
				root->value() < *rightMax;
		}

		if (minValue)
		{
			*minValue = min(min(*leftMin, *rightMin), root->value());
		}

		if (maxValue)
		{
			*maxValue = max(max(*leftMax, *rightMax), root->value());
		}
	}

	return ret;
}
#endif

bool isBinarySearchTree(shared_ptr<BinaryTreeNode<int>> root, 
	int min = numeric_limits<int>::min(), 
	int max = numeric_limits<int>::max())
{
	if (!root)
	{
		return true;
	}

	if (root->value() <= min || root->value() > max)
	{
		return false;
	}

	return isBinarySearchTree(root->left(), min, root->value()) &&
		isBinarySearchTree(root->right(), root->value(), max);
}

void testIsBinarySearchTree()
{
	//Implement a function to check if a binary tree is a binary search tree.
	auto root = make_shared<BinaryTreeNode<int>>(0);
	for (int i = 1; i < 15; i++)
	{
		TreeHelper::add<int>(root, i);
	}

	if (isBinarySearchTree(root))
	{
		cout << "The given tree is binary search tree." << endl;
	}


	int array[] = {0, 1, 2, 3 ,4 ,5 ,6 ,7 ,8};
	vector<int> data(&array[0], &array[sizeof(array) / sizeof(int)]);

	auto ret = sortedUniqueArrayToBalancedBinarySearchTree(data.begin(), data.end());
	if (isBinarySearchTree(ret))
	{
		cout << "The given tree is binary search tree." << endl;
	}
}

void testFindNextNode()
{
	//4.6 Write an algorithm to find the 'next' node (i.e. in-order successor) of a given node in a binary 
	//search tree. You may assume that each node has a link to its parent.
	
	int array[] = {0, 1, 2, 3 ,4 ,5 ,6 ,7 ,8};
	vector<int> data(&array[0], &array[sizeof(array) / sizeof(int)]);

	auto root = sortedUniqueArrayToBalancedBinarySearchTree(data.begin(), data.end());


}

bool findFirstNode(
	shared_ptr<BinaryTreeNode<int>>root, 
	shared_ptr<BinaryTreeNode<int>> node)
{
	if (!root)
	{
		return false;
	}

	if (root->left() && findFirstNode(root->left(), node))
	{
		return true;
	}
	else if (root->right() && findFirstNode(root->left(), node))
	{
		return true;
	}
	else
	{
		return false;
	}
}

shared_ptr<BinaryTreeNode<int>> findFirstCommonAncestor(
	shared_ptr<BinaryTreeNode<int>>root, 
	shared_ptr<BinaryTreeNode<int>> first, 
	shared_ptr<BinaryTreeNode<int>> second)
{
	if (root == nullptr)
	{
		return nullptr;
	}

	auto left = findFirstCommonAncestor(root->left(), first, second);
	if (left && left != first && left != second)
	{
		return root->left();
	}

	auto right = findFirstCommonAncestor(root->right(), first, second);
	if (right && right != first && right != second)
	{
		return root->right();
	}

	if (left && right)
	{
		return root;
	}
	else if (root == first ||root == second)
	{
		return root;
	}
	else
	{
		return left ? left : right;
	}
}

void testFindFirstCommonAncestor()
{
	//4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary
	//tree. Avoid storing additional nodes in a data stucture. NOTE: This is not necessarily a binary
	//search tree.

	auto root = make_shared<BinaryTreeNode<int>>(0);
	vector<shared_ptr<BinaryTreeNode<int>>> nodes;
	nodes.push_back(root);

	for (int i = 1; i < 15; i++)
	{
		nodes.push_back(TreeHelper::add<int>(root, i));
	}

	shared_ptr<BinaryTreeNode<int>> ret = findFirstCommonAncestor(root, nodes[3], nodes[4]);
	if (ret)
	{
		cout << "The first common ancesstor is " << ret->value() << endl;
	}
}

bool matchTree(shared_ptr<BinaryTreeNode<int>> tree1, shared_ptr<BinaryTreeNode<int>> tree2)
{
	if (!tree1 && !tree2)
	{
		return true;
	}

	if (tree1->value() != tree2->value())
	{
		return false;
	}

	return matchTree(tree1->left(), tree2->left()) && 
		matchTree(tree1->right(), tree2->right());
}

bool isSubtree(shared_ptr<BinaryTreeNode<int>> tree1, shared_ptr<BinaryTreeNode<int>> tree2)
{
	if (!tree1 || !tree2)
	{
		return false;
	}

	if (tree1->value() == tree2->value())
	{
		return matchTree(tree1, tree2);
	}

	return isSubtree(tree1->left(), tree2) || isSubtree(tree1->right(), tree2);
}

void testcontainsTree()
{
	//You have two very large binary tree T1, with millions of nodes, and T2, with hundres of nodes.
	//Create an algorithm to decide if T2 is a subtree of T1.
	//A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is idential
	//to T2. That is, if you cut off the tree at node n, the two trees would be idential.

	auto tree1 = make_shared<BinaryTreeNode<int>>(0);
	for (int i = 1; i < 150; i++)
	{
		TreeHelper::add<int>(tree1, i);
	}

	auto tree2 = make_shared<BinaryTreeNode<int>>(0);
	for (int i = 1; i < 150; i++)
	{
		TreeHelper::add<int>(tree2, i);
	}

	if (isSubtree(tree1, tree2))
	{
		cout << "tree2 is subtree of tree1." << endl;
	}
}

void printPathsSumsToGivenValue(shared_ptr<BinaryTreeNode<int>> node, int sum, vector<int> path, int level)
{
	if (!node)
	{
		return;
	}

	path[level] = node->value();
	int temp = 0;
	for (int i = level; i >= 0; i--)
	{
		temp += path[i] ;
		if (temp == sum)
		{
			//print
			for (int j = i; j <= level; j++)
			{
				cout << path[j] << ",";
			}
			cout << endl;
		}
	}

	printPathsSumsToGivenValue(node->left(), sum, path, level + 1);
	printPathsSumsToGivenValue(node->right(), sum, path, level + 1);
}

void testFindPathsSumToGivenValue()
{
	//You are given a binary tree in which each node contains a value. Design an algorithm to print all 
	//paths which sum to a given value. The path does not need to start or end at the root or a leaft.

	auto root = make_shared<BinaryTreeNode<int>>(0);
	for (int i = 1; i < 150; i++)
	{
		TreeHelper::add<int>(root, i);
	}

	auto height = TreeHelper::height(root);
	vector<int> path(height);

	printPathsSumsToGivenValue(root, 15, path, 0);
}

int _tmain(int argc, _TCHAR* argv[])
{
	//testIsBalancedBTree();
	//testSortedUniqueArrayToBalancedBinarySearchTree();
	//testBinaryTreeToLinkedList();
	//testIsBinarySearchTree();
	//testFindNextNode();
	//testFindFirstCommonAncestor();
	//testcontainsTree();
	testFindPathsSumToGivenValue();
    cin.get();
	return 0;
}

